package src;

import java.util.HashMap;
import java.util.Map;

/**
 * @version : 1.0.0
 * @author：jacky
 * @date : 2020/1/19
 * <p>
 * 旋转数组中的最小元素
 * 把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转，
 * 输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。
 */
public class Six_RotateArray {

    //TODO 解题思路
    /**
     * 个人觉得题目没有说的很清楚，在一个递增数组中做一次旋转，给出旋转后的数组
     * 找到最小元素
     * 有个比较暴力的方法，如果前一个元素大于后一个元素，说明旋转了，则找到了最小的元素
     * 如果前一个元素一直小于后一个元素，说明没有旋转，返回第一个元素就可以
     *
     * 另一种就是用二分查找法，如果中间元素位于递增，则中间>右边，这时候最小元素在后半部分
     * 反之，最小元素在前半部分
     */

    public int minNumberInRotateArray(int [] array) {

        int length = array.length - 1;
        if (length == 0)
            return array[0];

        for(int i = 0;i<length;i++){
            if (array[i] > array[i+1])
                return array[i+1];
        }
        //返回第一个元素
        return array[0];
    }

}


class Solution {
    public int distinctEchoSubstrings(String text) {
        Map<String, Integer> map = new HashMap<>();
        int j = 1;
        int len = text.length();


        for (int i = 0; i < len; i++) {
            j = i + 1;
            while (j + j - i <= len) {
                String str0 = text.substring(i, j);
                String str1 = text.substring(j, j - i + j);
                j++;
                if (str0.equals(str1)) {
                    map.put(str0, map.getOrDefault(str0, 0) + 1);
                }
            }
        }
        return map.size();
    }
}
